# 三数之和
a = [-1, 0, 1, 2, -1, 4]


def two_sum(nums: list, start, target):
    lo = start
    hi = len(nums) - 1
    rs = []
    while lo < hi:
        s = nums[lo] + nums[hi]
        left = nums[lo]
        right = nums[hi]
        if s == target:
            rs.append([nums[lo], nums[hi]])
            while lo < hi and nums[lo] == left:
                lo += 1
            while lo < hi and nums[hi] == right:
                hi -= 1
        elif s > target:  # 最大值加上左边的都大于target所以左移右指针
            while lo < hi and nums[hi] == right:
                hi -= 1
        elif s < target:
            while lo < hi and nums[lo] == left:
                lo += 1
    return rs


print(two_sum(a, 0, 4))

a = [1, 1, 1, 2, 3]  # target = 6 重复测试


def three_sum(nums: list, target):
    n = len(nums)
    res = []
    temp_index = 0  # 存储临时下标
    for i, v in enumerate(nums):
        if i <= temp_index:
            continue
        # print('i=%d' % i)
        # 对 target - nums[i] 计算 twoSum
        t = two_sum(nums, i + 1, target - nums[i])
        # 如果存在满足条件的二元组，再加上 nums[i] 就是结果三元组
        # print(t)
        for j in t:
            j.append(nums[i])
            res.append(j)
        # 跳过第一个数字重复的情况，否则会出现重复结果
        while temp_index < n - 1 and nums[temp_index] == nums[temp_index + 1]:
            temp_index += 1
            # print(temp_index)
    return res


print(three_sum(a, 6))
